package mr

import (
	"fmt"
	"time"
)

// max tasks
const MAXIMUM_CAPACITY int = 1 << 30

// max delay time: one day.
const MAXDELAY int = 24 * 60 * 60

// Level of TimeWheel
type Level int

const (
	Second Level = iota
	Mintue
	HOUR
	END
)

// as we konw, in a real clock,
// hour cycle has 24 slots,
// and minut or second has 60 slots.
var slots map[Level]int = map[Level]int{
	Second: 60,
	Mintue: 60,
	HOUR:   24,
}

/**
* a slot in TimeWheel,
* Elements: in one slot, we can stroe many task,
			useing map for look for a task with key
			if task is cancel, then map[task] = false
* expire  : time to excute task
* index   : index of solt in the clock
*/
type TimeWheelEntry struct {
	Elements []DelayQueueInterface
	expire   time.Time
	index    int
	level    Level

	// using in Mintue and Hour level
	// int        : 下一个轮盘的位置, interface{}: DelayQueueInterface 的集合
	// interface{}: if level is Minute, then interfcee{} is DelayQueueInterface
	//              if level is Hour,   then interface{} is map[DelayQueueInterface]interface{}
	Under *map[int][]DelayQueueInterface
}

/**
 * we can see TimeWheel as a cycle in a real clock.
 * there are three type of TimeWheel, hour, minute and second.
 *
 * overflow: hour's overflow is nil,
 *           minute's overflow is hour,
 *           second's overflow is minute
 * entrys  : element in entrys is TimeWheelEntry
 * capacity: hour's capacity is 24,
 *           minute's and second's capacity is 60
 * point   : the pointer of real time in clock
 * queue   : all tasks
 */
type TimeWheel struct {
	overflow  *TimeWheel
	underflow *TimeWheel
	entrys    []*TimeWheelEntry
	capacity  int
	point     int
	level     Level
	queue     DelayQueue

	m *Master
}

func MakeTimeWheel() *TimeWheel {
	p := makeTimeWheel(Second, time.Now(), nil)
	p.queue = DelayQueue{A: make(Elements, 0)}
	p.queue.Init()

	for i := 0; i < len(p.entrys); i++ {
		t := time.Now()
		var delay int
		if t.Second() < i {
			delay = i - t.Second()
		} else {
			delay = 60 + i - t.Second()
		}
		p.entrys[i].expire = t.Add(time.Duration(delay) * time.Second)
		p.queue.Offer(p.entrys[i])
	}
	go func() {
		for {
			time.Sleep(time.Second)

			entry := p.fresh()
			go p.ExpiredElemets(entry)
			p.AdvanceClock()

			if p.m.Done() {
				return
			}

			// fmt.Printf("point=%v, time=%v\n", p.point, time.Now())
		}
	}()

	return p
}

func (p *TimeWheel) ExpiredElemets(entry *TimeWheelEntry) {
	// fmt.Printf("expire(%v), now(%v), len=%v\n", (entry.expire), time.Now(), len(entry.Elements))

	res := make([]DelayQueueInterface, 0)
	for _, x := range entry.Elements {
		d := x.(DelayQueueInterface)
		if !d.Done() {
			// fmt.Printf("【TimeWheel】超时任务: expire(%v), now(%v), task=%v\n", d.Expired(), time.Now(), x.(*DelayTask).id)
			res = append(res, d)
		}
	}
	p.m.handleExpiredTask(res)
}

func (p *TimeWheel) SetMaster(m *Master) {
	p.m = m
}

func (p *TimeWheel) fresh() *TimeWheelEntry {
	entry := p.queue.Poll().(*TimeWheelEntry)
	entry.expire = time.Now().Add(time.Minute)
	p.queue.Offer(entry)
	return entry
}

func (p *TimeWheel) AdvanceClock() {
	s := slots[p.level]
	point := p.point

	if point == s-1 {
		if p.overflow != nil {
			p.overflow.AdvanceClock()
		}
		p.point = 0
	} else {
		if p.level == Second {

		} else if p.level == Mintue || p.level == HOUR {
			entry := p.entrys[(p.point+1)%slots[p.level]]
			// fmt.Printf("推进(level=%d) ...., point=%v, entryIndex=%v, address=%v\n", p.level, p.point, entry.index, entry.Under)
			for k, v := range *entry.Under {
				// fmt.Printf("k=%d, len(k)=%d\n", k, len(v))
				// if len(v) > 0 {
				// 	fmt.Println("=====hahahah===")
				// }
				p.underflow.entrys[k].Elements = append(p.underflow.entrys[k].Elements, v...)
			}
		}
		p.point++
	}
	p.entrys[point].Elements = make([]DelayQueueInterface, 0)
}

func (p *TimeWheel) AddTask(x DelayQueueInterface) bool {
	delay := int(x.Delay())
	if delay > MAXDELAY || delay <= 0 {
		return false
	}
	p.innerAddTask(Second, delay, 1, x)
	// fmt.Println("==============")
	return true
}

func (p *TimeWheel) CancelTask(x DelayQueueInterface) {

}

func (p *TimeWheel) innerAddTask(l Level, delay int, base int, x DelayQueueInterface) {
	// fmt.Printf("[AddTask 1] delay: %d, l: %d, point:%d, now:%v\n", delay, l, p.point, time.Now())

	if delay < slots[l] {

		entryIndex := (delay + p.point) % slots[p.level]

		// fmt.Printf("[AddTask 2] entryIndex: %d, base : %d \n", entryIndex, base)

		p.entrys[entryIndex].Elements = append(p.entrys[entryIndex].Elements, x)
		// fmt.Printf("after put current: len=%d\n", len((p.entrys[entryIndex].Elements)))

		if p.underflow != nil {
			underSlotIndex := ((int)(x.Delay())%base + p.underflow.point) % slots[p.level]
			// fmt.Printf("[AddTask 2] underSlotIndex: %d, base: %d, level: %d\n", underSlotIndex, base, p.level)

			(*p.entrys[entryIndex].Under)[underSlotIndex] = append((*p.entrys[entryIndex].Under)[underSlotIndex], x)
			// fmt.Printf("--after put underflow: len=%d, address=%v\n", len((*p.entrys[entryIndex].Under)[underSlotIndex]), (*p.entrys[entryIndex].Under))
		}

	} else {
		p.overflow.innerAddTask(l+1, delay/slots[l], base*slots[l], x)
	}

}

func makeTimeWheel(l Level, t time.Time, under *TimeWheel) *TimeWheel {
	if l == END {
		return nil
	}
	s := slots[l]
	capacity := capacityForSlots(s)
	entrys := entrysForSlot(s, under)
	point := pointForLevel(l, t)

	p := &TimeWheel{
		entrys:    entrys,
		capacity:  capacity,
		level:     l,
		point:     point,
		underflow: under,
	}
	p.overflow = makeTimeWheel(l+1, t, p)

	return p
}

func capacityForSlots(s int) int {
	var n int = s - 1
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16

	if n < 0 {
		n = 1
	} else if n >= MAXIMUM_CAPACITY {
		n = MAXIMUM_CAPACITY
	} else {
		n = n + 1
	}
	return n
}

func entrysForSlot(s int, under *TimeWheel) []*TimeWheelEntry {
	entrys := make([]*TimeWheelEntry, s)
	for i := 0; i < len(entrys); i++ {
		entrys[i] = &TimeWheelEntry{
			index:    i,
			Elements: make([]DelayQueueInterface, 0),
		}

		if under != nil {
			t := make(map[int][]DelayQueueInterface)
			entrys[i].Under = &t
			for j := 0; j < slots[under.level]; j++ {
				(*(entrys[i].Under))[j] = make([]DelayQueueInterface, 0)
			}
		}
	}
	return entrys
}

func pointForLevel(l Level, t time.Time) int {
	switch l {
	case Second:
		return t.Second()
	case Mintue:
		return t.Minute()
	case HOUR:
		return t.Hour()
	}
	panic("Level is illegal")
}

func (t TimeWheelEntry) Delay() int64 {
	return int64(t.expire.Sub(time.Now()).Seconds())
}

func (t TimeWheelEntry) Expired() time.Time {
	return t.expire
}

func (t TimeWheelEntry) Done() bool {
	return false
}

func (p *TimeWheel) PrintEntrys() {
	_p := p
	for ; _p != nil; _p = _p.overflow {
		fmt.Printf("current level: %v\n", _p.level)
		for i, v := range _p.entrys {
			fmt.Printf("i=%d, index=%d, level=%d, len(Elements)=%d\n", i, v.index, v.level, len(v.Elements))
		}
		fmt.Println("=======================================================")
	}
}
